import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Leetcode1001 {
    public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {
        Map<Integer, Integer> row = new HashMap<>();
        Map<Integer, Integer> column = new HashMap<>();
        Map<Integer, Integer> diagonal = new HashMap<>();
        Map<Integer, Integer> antiDiagonal = new HashMap<>();
        Map<Integer, Set<Integer>> index = new HashMap<>();
        for (int[] lamp : lamps) {
            row.put(lamp[0], row.getOrDefault(lamp[0], 0) + 1);
            column.put(lamp[1], column.getOrDefault(lamp[1], 0) + 1);
            diagonal.put(lamp[0] - lamp[1], diagonal.getOrDefault(lamp[0] - lamp[1], 0) + 1);
            antiDiagonal.put(lamp[1] - lamp[0], antiDiagonal.getOrDefault(lamp[1] - lamp[0], 0) + 1);

            Set<Integer> ySet = index.getOrDefault(lamp[0], new HashSet<>());
            ySet.add(lamp[1]);
            index.put(lamp[0], ySet);
        }

        int[] res = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int[] query = queries[i];
            if (row.containsKey(query[0]) || column.containsKey(query[1]) || diagonal.containsKey(query[0] - query[1]) || antiDiagonal.containsKey(query[1] - query[0])) {
                res[i] = 1;
            }

        }

        return res;
    }


}
